package com.leetcode.partition1;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/8/4 10:04
 */
public class LC49字母异位词分组 {

    public static List<List<String>> groupAnagrams(String[] strs) {
        return hashtableMethod(strs);
    }

    public static void main(String[] args) {
//        String[] str = {"eat", "tea", "tan", "ate", "nat", "bat"};
        String[] str = {"bdddddddddd","bbbbbbbbbbc"};
        System.out.println(groupAnagrams(str));
    }

    //哈希表法
    private static List<List<String>> hashtableMethod(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        for (String str : strs) {
            String key = hashKey(str.toCharArray());
            System.out.println(key);
            if (map.containsKey(key)) {
                map.get(key).add(str);
                continue;
            }
            List<String> item = new ArrayList<>();
            item.add(str);
            map.put(key, item);
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }

    private static String hashKey(char[] array) {
        Map<Character, Integer> map = new HashMap<>(26);
        for (int i = 0; i < 26; i++) {
            map.put((char) ('a' + i), 0);
        }
        for (char c : array) {
            map.put(c, map.get(c) + 1);
        }
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            sb.append('#').append(entry.getValue());
        }
        return sb.toString();
    }

    //排序法
    private static List<List<String>> sorted(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        for (String str : strs) {
            //每一个异位单词，在排序后都应该是相同的
            String sortedStr = sortedString(str);
            if (map.containsKey(sortedStr)) {
                map.get(sortedStr).add(str);
                continue;
            }
            List<String> item = new ArrayList<>();
            item.add(str);
            map.put(sortedStr, item);
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }

    private static String sortedString(String str) {
        char[] array = str.toCharArray();
        Arrays.sort(array);
        return new String(array);
    }
}
